class Solution 
{
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) 
    {
        sort(nums.begin(), nums.end());

        vector<vector<int>> ans;
        
        int sz = nums.size();

        int i = 0;  // 固定第一个数
        while(i < sz)
        {
            int j = i + 1;  // 固定第二个数
            while(j < sz)  // 三数之和
            {
                int left = j + 1, right = sz - 1;
                long aim = (long)target - nums[i] - nums[j];
                while(left < right)
                {
                    int sum = nums[left] + nums[right];

                    if(sum > aim) --right;
                    else if(sum < aim) ++left;
                    else
                    {
                        ans.push_back({nums[i], nums[j], nums[left++], nums[right--]});
                        
                        // 去重 left and right
                        while(left < right && nums[left] == nums[left - 1]) ++left;
                        while(left < right && nums[right] == nums[right + 1]) --right; 
                    }
                }

                ++j;
                while(j < sz && nums[j] == nums[j - 1]) ++j;  // 去重 j
            }

            ++i;
            while(i < sz && nums[i] == nums[i - 1]) ++i;  // 去重 i
        }

        return ans;
    }
};